package com.gxc.array;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 46. 全排列
 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 */
public class Permute {

    public static void main(String[] args) {
        List<List<Integer>> permute = permute(new int[]{1, 2, 3});
        print(permute);
    }
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        recursion(0 , nums, list, res);
        return res;
    }

    public static void recursion(int i, int[] num, List<Integer> list, List<List<Integer>> res) {
        if (i == num.length) {
            res.add(new ArrayList<>(list));
            return;
        }

        for (int j = 0; j < num.length; j++) {
            if (list.contains(num[j])) continue;
            list.add(num[j]);
            recursion(i+1, num, list, res);
            list.remove((Object)num[j]);
        }
    }

    private static void print(List<List<Integer>> list) {
        for (int i = 0; i < list.size(); i++) {
            List<Integer> list1 = list.get(i);
            for (int j = 0; j < list1.size(); j++) {
                System.out.print(list1.get(j) + " ");
            }
            System.out.println("");
        }
    }

}
